#include <bits/stdc++.h>
using namespace std;

/*
2787. 将一个数字表示成幂的和的方案数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你两个 正 整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。

 

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。
示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。
 

提示：

1 <= n <= 300
1 <= x <= 5
*/

// 法一
class Solution {
public:
    using ll = long long;
    int numberOfWays(int n, int x) {
        // 状态转移方程
        const int MOD = 1e9 + 7;
        // k ^ x <= n 所有底数k
        vector<ll> powers;
        for (int k = 1; ; k++) {
            ll power = 1;
            bool overflow = false;  // 溢出状态量
            for (int i = 0; i < x; i++) {
                if (power > n / k) {
                    overflow = true;
                    break;
                }
                power *= k;
                if (power > n) {
                    overflow = true;
                    break;
                }
            }
            if (overflow)   break;
            powers.push_back(power);
        }

        // 前i个底数表示j的方案数
        int m = powers.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[0][0] = 1;

        // 迭代来使用底数
        for (int i = 1; i <= m; i++) {
            ll p = powers[i - 1];
            for (int j = 0; j <= n; j++) {
                // 不使用第i个底数
                dp[i][j] = dp[i - 1][j];
                // 使用第i个底数
                if (j >= p)     dp[i][j] = (dp[i][j] + dp[i - 1][j - p]) % MOD;
                
            }
        }
        return dp[m][n];
    }
};

// 法二
class Solution {
public:
    using ll = long long;
    int numberOfWays(int n, int x) {
        const int MOD = 1e9 + 7;
        
        // 找出所有可能的底数k，使得k^x <= n
        vector<ll> powers;
        for (int k = 1; ; k++) {
            ll power = 1;
            bool valid = true;
            for (int i = 0; i < x; i++) {
                if (power > n / k) { // 防止溢出
                    valid = false;
                    break;
                }
                power *= k;
            }
            if (!valid || power > n) break;
            powers.push_back(power);
        }
        
        // 优化空间的动态规划
        vector<int> dp(n + 1, 0);
        dp[0] = 1; // 初始条件
        
        for (ll p : powers) {
            // 从后往前更新，避免重复使用同一个底数
            for (int j = n; j >= p; j--) {
                dp[j] = (dp[j] + dp[j - p]) % MOD;
            }
        }
        
        return dp[n];
    }
};

// 法二优化
class Solution {
public:
    using ll = long long;
    int numberOfWays(int n, int x) {
        const int MOD = 1e9 + 7;
        
        // 找出所有可能的底数k，使得k^x <= n
        vector<long long> powers;
        for (int k = 1; ; k++) {
            long long power = pow(k, x);
            // 处理pow函数可能的精度问题
            if (power > n || power < 0) break; // power < 0 表示溢出
            powers.push_back(power);
        }
        
        // 优化空间的动态规划
        vector<int> dp(n + 1, 0);
        dp[0] = 1; // 初始条件
        
        for (long long p : powers) {
            // 从后往前更新，避免重复使用同一个底数
            for (int j = n; j >= p; j--) {
                dp[j] = (dp[j] + dp[j - p]) % MOD;
            }
        }
        
        return dp[n];
    }
};

// 法三
class Solution {
public:
    int numberOfWays(int n, int x) {
        // dp[j] 表示将数字j表示为若干个互不相同正整数的x次幂之和的方案数
        long long dp[n + 1];
        // 初始化dp数组为0，所有数字初始方案数为0
        memset(dp, 0, sizeof(dp));
        // 初始条件：组成数字0有1种方案（使用空集合）
        dp[0] = 1;
        
        // 遍历所有可能的底数i，计算i的x次幂v
        // 当v > n时，该底数及更大的底数都无法参与组成n，停止循环
        for (int i = 1, v; ; i++) {
            // 计算当前底数i的x次幂v
            v = pow(i, x);
            // 若v超过n，后续i的幂会更大，无需继续计算
            if (v > n) break;
            
            // 从n往v反向遍历，更新dp数组
            // 反向遍历确保每个幂值v只被使用一次（0-1背包思想）
            for (int j = n; j >= v; j--) {
                // 对于数字j，新增的方案数等于组成j-v的方案数（即使用当前v的情况）
                dp[j] += dp[j - v];
            }
        }
        
        // 返回组成n的方案数，结果对1e9+7取余
        return dp[n] % static_cast<int>(1e9+7);
    }
};